
\chapter{The Structure of the Input}


 
% How can we define words then? We assume that each word refers 
% Let us assume that a word consists of a Stem, Affixes


We view {\em statistical parsing} of  {morphologically rich languages}  as a structure prediction task where we aim to induce  a prediction function  \(f:\mathcal{X}\rightarrow{Y}\), where \(\mathcal{X}\) is a sentence in an MRL   and \(\mathcal{Y}\) is a syntactic parse-tree, from a set of annotated examples.  To the function \(f\) we first need to  define the input and output spaces,   \(\mathcal{X}\) and \(\mathcal{Y}\), respectively. 
In  English parsing, \(x\in\mathcal{X}\) is  a sequence of words from a finite vocabulary \(\Sigma\), that is, \(x\in \Sigma^*\). \(\mathcal{Y}\) contains parse trees with elements of \(\Sigma\) as nodes in the trees. In MRLs, elements in \(x\) have a more complex internal structure, and thus are not necessarily contained in  \(y\in\mathcal{Y}\)  as is. In this chapter we  concentrate on  defining \(x\in\mathcal{X}\) 
The next chapter will in turn examine the  intricate relation of elements in \(\mathcal{X}\) to the formal syntactic structures in \(\mathcal{Y}\), and how the  parsers may learn to predict such structures.
When parsing morphologically languages, it is  crucial to understand and model correctly  the structure of the input signal, otherwise, the parsing results may be unpredictable or uninterpretable.
 This chapter is dedicated to formally define what are words, what is the input signal to the parser, and what is the relation between them.
 
 %The longest word in German.

 
  \section{The Structure of the Lexicon}


A sentence \(x\in \mathcal{X}\) in an MRL  contains a sequence of potentially-complex space-delimited  tokens.
 %that do not map directly onto words in closed set \(\Sigma\). 
 In order to   describe these tokens formally, let us  first define  a MRLon, i.e., a morphologically rich lexicon.
\begin{itemize}
\item Let \(\mathcal{L}\) be a finite set of   lemmas (a.k.a.\ word senses)
\item Let \(\mathcal{C}\) be a set of  grammatical categories (a.k.a.\ part-of-speech tags)
\item Let \(\mathcal{A}\) be a set of  possible attribute names (a.k.a.\ features or properties)
\item Let \(\mathcal{V}\) be a set of  possible attributes values (a.k.a.
 feature values or assignment)
\end{itemize}
For brevity, we denote  \(\mathcal{V}_A\)  the set of values that an attribute \(A\in\mathcal{A}\) may be assigned. 

A  lexicon entry \(e\) is a tuple: \[e=\langle l, c, b\rangle\] 

such that \(b\) is a property bundle denoting a set of attribute:value pairs
  \[b=\{a:v|a\in \mathcal{A}, v\in \mathcal{V}_a\}\]


We define the  morphosyntactic representation (MSR) of an entry \(\langle l,c,b\rangle\)  to be  \( \langle c,b \rangle \).
Examples for lexical entries for a  fragment  of English are given in Table \ref{lex:e}. Note that all entries  contain an MSR, but the lemma \(l\) might remain empty in case of  functional  entries (a.k.a.\ function words). The MSR \(b\)  may be empty  in case no  grammatical properties are indicated morphologically beyond the core word-sense. The category \(c\) is mandatory.\footnote{\url{http://en.wikipedia.org/wiki/A_Boy_Named_Sue}} 

\begin{table}\center
\scalebox{0.9}{\begin{tabular}{|r|cll|}
\hline
``Lucy" & Lucy & NN & \{gender:feminine, number:singular\}\\
``Lucy" & Lucy & NN & \{gender:masculine, number:singular\}\\
``snowing" & snow & VB & \{tense:present\} \\
%``snowing" & snowing & NN & \{countable:-\} \\
``apples" & apple & NN & \{number:plural,countable:+\} \\
``sings" & sing & V & \{person:3,number:singular,tense:present\} \\
``the" & - & DET & \{definitness:+\} \\
``a" &  - & DET & \{definitness:-\} \\
``will" & -  & AUX & \{tense:future\} \\
``is" &  - & COP & \{person:3,number:singular,tense:present\} \\
``his" &  - & PRP\$ & \{gender:masculine, number:singular\} \\
``yesterday" &  yesterday & RB & - \\
``knowingly" &  knowingly & RB & - \\
\hline
\end{tabular}}
\caption{A morphologically-rich lexicon for a fragment of English}\label{lex:e}
\end{table}

\paragraph{Some observations on Table \ref{lex:e}}

\begin{itemize}
\item The  word "knowingly" does not decompose into lemma and features as distinct entries in the MRLon. A derivational process  fused the semantics of  "knowing"+"ly" to obtain this adverbial,  but for the purpose of \emph{syntactic} parsing, all semantically-bearing derivational processes must have already taken place. One reason for that is that derivational morphemes encode semantic information that may also change the category \(c\) of the token(in the  "knowingly" example V has  changed to RB), but in order to proceed with syntactic parsing, we want to view the category \(c\) as fixed. \item Note  that the  word "sings" does not decompose into "sing" and "s" as distinct entries in the MRLon.  "s" is an inflectional morpheme that adds features (third person singular) to the syntactic category, and does not carries its own part of speech tag.  In order to proceed with syntactic parsing, we want to view the category \(c\) as mandatory.
\item  You might wonder, at some later point, what distinguished a single  lexical entry with many features from a complex token that contains multiple entries. A rule of thumb  is  that the number of independent POS categories defines the number of lexicon entries "lumped together" in a token.  E.g., "knowing" is a verb marked with tense features, and "ing" can not be a standalone entry with its own syntactic category. A word like "won't" contains two different POS tags, "will" (AUX) and "not" (RB) and thus we do separate them into separate morphemes.  In order to proceed with syntactic parsing, we want to view the category \(c\) as unique.

\end{itemize}
Even though we referred to a wide range of morphologically rich phenomena, the MRLon is an organizational principle that may fit {\em any} language and we easilt applied it to English.
In morphology-free (isolating) languages, the definition of lexicon entry collapses with the definition of a tagged word.

%\subsection{Morphological  Analysis}

Let us assume a MRLon \({\Sigma}\). We define a morphologically rich language as a triplet 
\[L = \langle \mathcal{T}, \Sigma, O\rangle \] 

such that:
\begin{itemize}
\item \(\mathcal{T}\) is a finite set of  space-delimited tokens 
\item \({\Sigma}\) is a finite set of lexical entries 
\item  \(O \) is a finite set of aggregation operations that may aggregate  lexical entries.\footnote{Such aggregation operations may go beyond simple concatenation. This shall not matter to us in our upcoming discussion. }
\end{itemize}

We require that \(\forall t\in \mathcal{T} :\exists_{m_1...m_n \in {\Sigma}, \oplus_1 ... \oplus_n\in O}  : ((m_1 \oplus_1 m_2).... \oplus_n m_n) =t\) 

An example of complex space-delimited tokens for English is given in Table \ref{eng:tokens}.



A token \(t\in \mathcal{T}\) may be {\em spelled-out} as a sequence of lexicon entries \(e_1...e_n\)  which  were aggregated to form a single space-delimited unit in written text.  We will formally denote all possible spellouts as a relation between a tokens and sequence of MRLon entries.
 \[S= \mathcal{T}\times {\Sigma}^*\] 
By definition, each space-delimited token must have at least one element in this set. 
%
Ambiguity  arises when there are multiple spellout possibilities for a single token. A simple example for spellout ambiguity in English, is, for instance, "Lucy" which can be spelled out in two ways, both contain a single entry, with gender feminine or masculine respectively. A more complex spellout ambiguity as found in Hebrew as shown in tables \ref{heb:lex} and \ref{heb:tok}.


For any MRL we assume a morphological analysis function  which assigns to each token,  all of its spellout possibilities (that is, a set of sequences of MRLon entries).
\[\mathcal{M}: \mathcal{T}\rightarrow\mathcal{P}({\Sigma}^*)\] 



\begin{table}\center
\begin{tabular}{|r|c|}
\hline
``aren't" &  are + not \\
``won't" &  will + not \\
``John's" &  John + his\\
\hline
\end{tabular}
\caption{Complex space-delimited tokens in English}\label{eng:tokens}
\end{table}


 \begin{table}\center
\begin{tabular}{|r|c|}
\hline
``BCLM" &  B + CL + FL + HM \\
``BCLM" &  BCL + FL + HM \\
``BCLM" &  B+CLM \\
\hline
\end{tabular}
\caption{An ambiguous space-delimited token in Hebrew}\label{heb:tok}
\end{table}


\begin{table}\center
\begin{tabular}{|r|cll|}
\hline
``B" & in & IN & - \\
``FL" & of & IN & - \\
``CL" & shadow & NN & \{gender:masculine, number:singular\} \\
``HM" & they & PRP & \{gender:masculine, number:plural,case:nom\} \\
\hline
\end{tabular}
\caption{A morphologically-rich lexicon for a fragment of Hebrew}\label{heb:lex}

\end{table}

%\subsection{Morphological Disambiguation}
Let \(L= T_L,\Sigma_L, O_L\) define a morphologically rich language. 
%and let \(\mathcal{S}\)  be the set of all sequences composed of elements from \({S_L}\), that is, \(\mathcal{S}={S_L}^*\).  
A sentence \(x\in\mathcal{X}\) is  defined to be \(x=x_1.... x_n\) where \(\forall i :x_i\in T_L\).

Let \({S_L}\) be the set of valid spellouts over \(\Sigma_L, O_L\).
Every token \(x_i\in T_L\) can have multiple spellouts, that is a set of elements from \(S_L\).
% that is \[\{ (x_i,s) |(x_i,s) \in S_L\} \geq 1\]
%\(x\in T_L,SP,t\in \mathcal{S}^*:s1...snSPt, x=s_1...s_n\)
%A sentence in a Morphology Rich Language (MRL) L is a sequence of tokens: \(x=x_1...x_n\)
A morphological analysis function  is a function mapping a token  in \(T_L\) to a set of spellout possibilities:
\[\mathcal{M}(x_i) = \{(x_i,s_1) , (x_i,s_2)  ... (x_i,s_n)\}\] where \[(x_i, s_j)\in {S_L}^*\]
Note that by our definition of an MRL it is always the case that \(|\mathcal{M}(x_i)|>0\) (even if  we have not seen that token before).
For a sentence \(x=x_1...x_n\), \(\mathcal{M}\) is the concatenation of the individual \(M(x_i)\).
\[\mathcal{M}(x)= \mathcal{M}(x_1)+\mathcal{M}(x_2)...+\mathcal{M}(x_n)\]
We define a  mapping \(\gamma\) to be a set of ordered pairs of words and their correct spellout:
\[\gamma=\{(x_i,e_1... e_{m_i})|e_1...e_{m_i} \in \Sigma\}\]

%A sentence mapping \(s^*\) is a function from tokens to their correct spellout in context.

%A spelled out sentence is a concatention   of the spellouts of \(x\), given S:
%\(S_M=s0s01..s0js11..s1k...sn1..snl\) where s0is the special token ROOT.


The  of {\em morphological disambiguation}  picks out a mapping for a sentence \(x\in\mathcal{X}\).  Without context this would be  impossible. With contect disambiguation may still be hard, even for a human hearer ("Lucy sleeps"). Dependending on extra-linguistic factors, different decisions may be taken. We will later define \(s^*\) as the probabilistic (or highest scoring) choice of \(\gamma\).

\[s^* = argmax_{s\in\mathcal{M}(x)} P(s|x)\]

%We understand \(s^*\) as the correct spellout (or correct segmentation, in the simple case) of a word in context.



\[s^* = argmax_{s\in\mathcal{M}(x)} Score(s,x)\]

  \section{The Source of the Lexicon}

\subsection{Data-Driven Lexica}

\subsection{External Lexica}

\subsection{Raw Data}

\section{Summary and Further Reading}
%\section{Morphological Analysis and Disambiguation}